#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include <vector>
#include <map>

using namespace std;

class UnderflowException
{
};

template <typename Unique, typename Comparable>
struct DataBase
{
    Unique key;
    Comparable data;

    DataBase() {}
    DataBase(const Unique &key, const Comparable &data) : key(key), data(data) {}
    DataBase(const DataBase &other) : key(other.key), data(other.data) {}
    DataBase(DataBase &&other) : key(std::move(other.key)), data(std::move(other.data)) {}

    DataBase &operator=(const DataBase &other)
    {
        this->key = other.key;
        this->data = other.data;
        return *this;
    }
};

template <typename Unique, typename Comparable>
class PriorityQueue
{
public:
    using This_DataBase = DataBase<Unique, Comparable>;

    explicit PriorityQueue(int capacity = 100)
        : array(capacity + 1), currentSize{0}
    {
    }

    explicit PriorityQueue(const vector<This_DataBase> &_input)
        : array(_input.size() + 10), currentSize(_input.size())
    {
        buildHeap(_input);
    }

    bool isEmpty() const
    {
        return currentSize == 0;
    }

    /**
     * @brief Find the smallest item in the priority queue.
     * Return the smallest item, or throw Underflow if empty.
     *
     * @return const This_DataBase&
     */
    const This_DataBase &findMin() const
    {
        if (isEmpty())
            throw UnderflowException{};
        return array[1];
    }

    /**
     * @brief Insert item x, allowing duplicates.
     *
     * @param x
     */
    void insert(const This_DataBase &x)
    {
        if (currentSize == array.size() - 1)
            array.resize(array.size() * 2);

        // Percolate up
        int hole = ++currentSize;
        array[hole] = x;
        percolateUp(hole);
    }

    /**
     * @brief Insert item x, without duplicates.
     *
     * @param x
     */
    void insert(This_DataBase &&x)
    {
        if (currentSize == array.size() - 1)
            array.resize(array.size() * 2);

        // Percolate up
        int hole = ++currentSize;
        array[hole] = std::move(x);
        percolateUp(hole);
    }

    /**
     * @brief Remove the minimum item.
     * Throws UnderflowException if empty.
     *
     */
    void deleteMin()
    {
        if (isEmpty())
            throw UnderflowException{};

        indices.erase(array[1].key);
        moveData(1, array[currentSize--]);
        percolateDown(1);
    }

    /**
     * @brief * Remove the minimum item and place it in minItem.
     * Throws Underflow if empty.
     *
     * @param minItem
     */
    void deleteMin(This_DataBase &minItem)
    {
        if (isEmpty())
            throw UnderflowException{};

        minItem = std::move(array[1]);
        indices.erase(minItem.key);
        moveData(1, array[currentSize--]);
        percolateDown(1);
    }

    void makeEmpty()
    {
        currentSize = 0;
    }

    /**
     * @brief Remove the item with Unique key k.
     * Do nothing if the item is not found.
     *
     * @param k
     */
    void remove(Unique k)
    {
        auto index = indices.find(k);
        if (index != indices.end())
        {
            indices.erase(index);
            moveData(index->second, array[currentSize--]);
            percolateDown(index->second);
        }
        else
        {
            cout << "No such key:" << k << endl;
        }
    }

    /**
     * @brief Modify the item with key k by increment d.
     *  Do nothing if no such item.
     *
     * @param k
     * @param d can be positive or negative.
     */
    void modifyData(Unique k, Comparable d)
    {
        auto index = indices.find(k);
        if (index != indices.end())
        {
            Comparable origin_data = array[index->second].data;
            array[index->second].data += d;
            Comparable New_data = array[index->second].data;
            if (New_data > origin_data)
                percolateDown(index->second);
            else if (New_data < origin_data)
                percolateUp(index->second);
        }
        else
        {
            cout << "No such key:" << k << endl;
        }
    }

private:
    int currentSize;             // number of elements in the heap
    vector<This_DataBase> array; // the heap array
    map<Unique, int> indices;    // std::map for stroring the index of element in the heap

    /**
     * @brief Establish heap order property from an arbitrary
     * arrangement of items. Runs in linear time.
     *
     */
    void buildHeap()
    {
        for (int i = currentSize / 2; i > 0; --i)
            percolateDown(i);
    }

    /**
     * @brief Internal method to percolate down in the heap.
     * hole is the index at which the percolate begins.
     *
     * @param _input
     */
    void buildHeap(const vector<This_DataBase> &_input)
    {
        for (int i = 0; i < _input.size(); ++i)
            array[i + 1] = _input[i];
        buildHeap();
    }

    /**
     * @brief Move the src element to index des
     * and update the index information in hash map.
     *
     * @param des
     * @param src
     */
    void moveData(int des, This_DataBase &src)
    {
        indices[src.key] = des;
        array[des] = std::move(src);
    }

    /**
     * @brief Internal method to percolate down in the heap.
     * hole is the index at which the percolate begins.
     *
     * @param hole
     */
    void percolateDown(int hole)
    {
        int child;
        This_DataBase tmp = std::move(array[hole]);

        for (; hole * 2 <= currentSize; hole = child)
        {
            child = hole * 2;
            if (child != currentSize && array[child + 1].data < array[child].data)
                ++child;
            if (array[child].data < tmp.data)
                moveData(hole, array[child]);
            else
                break;
        }
        moveData(hole, tmp);
    }

    /**
     * @brief Internal method to percolate up in the heap.
     * hole is the index at which the percolate begins.
     *
     * @param hole
     */
    void percolateUp(int hole)
    {
        This_DataBase tmp = std::move(array[hole]);

        for (; hole > 1 && tmp.data < array[hole / 2].data; hole /= 2)
            moveData(hole, array[hole / 2]);
        moveData(hole, tmp);
    }
};

#endif